package _01_动态数组;

import java.util.Arrays;

public class _416_分割等和子集 {

    public static void main(String[] args) {

        _416_分割等和子集 v = new _416_分割等和子集();

        int[] ins = {1, 2, 5};
        System.out.println(v.canPartition(ins));

    }

    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        if (total % 2 != 0) return false;
        int half = total >> 1;
        Arrays.sort(nums);

        return dfs(nums, half, 0);
    }

    private boolean dfs(int[] nums, int half, int index) {
        if (half == 0) {
            return true;
        }

        for (int i = index; i < nums.length; i++) {
            if (half >= nums[i]) {
                if (dfs(nums, half - nums[i], i + 1)) {
                    return true;
                }
            }
        }
        return false;
    }

}
